Nearly all forms of electronic communication and storage systems use error-correcting codes. Error correcting codes compensate for the intrinsic unreliability of information transfer in these systems by introducing redundancy into the data stream. The mathematical foundations of error correcting were established by the Shannon-Hartley theorem, which defines for the channel a capacity, a quantity that specifies the maximum rate at which information can be reliably delivered through the channel.
Reliable transmission at rates approaching capacity requires the use of error correcting codes. Thus, error correcting codes are designed to achieve sufficient reliability while approaching capacity as closely as possible. The complexity of implementing the error correcting code is an additional factor that always comes into play in practical applications of error correcting codes. Recent advances in error correcting coding systems resulting from the invention of turbo codes and the subsequent rediscovery and development of low-density parity-check (“LDPC”) codes offer coding systems of feasible complexity that can approach the Shannon-Hartley theorem capacity quite closely.
LDPC codes are defined by a sparse parity-check matrix H. This sparse matrix is often randomly generated, subject to the sparsity constraints. A valid codeword, x, based on a given parity check matrix, H, must satisfy the condition 0=Hx, where 0 is the all zeros vector. FIG. 1 illustrates an example sparse parity check matrix H for an LDPC code having a length of 12 (i.e., 12 columns in the matrix). Each row of the parity check matrix H represents a set of check equations that XOR to 0.
LDPC codes are well represented by bipartite graphs, often called Tanner graphs. FIG. 2 illustrates an example Tanner graph 20. Tanner graph 20 represents the parity check matrix, H, in which one set of nodes, the variable nodes 22, corresponds to bits of the codeword, and the other set of nodes, the check nodes 26, sometimes called constraint nodes, correspond to the set of parity check constraints which define the code. Edges 24 in the graph connect variable nodes 22 to check nodes 26. A variable node and a check node are said to be neighbors if they are connected by an edge in the graph. The number of connections on a check node is called check node degree dc or row weight. A decoder calculates a log-likelihood ratio (“LLR”) for each of the bits according to variable nodes 22 connected by an edge 24 with a particular check node. The calculation is an iterative process that takes into account LLR values associated with each of the other variable nodes 22. Since the process is iterative, the calculation of the LLRs for each variable node 22 continues in successive passes updating the LLR value associated with each variable node 22 associated with one check node until the criteria for stopping the process has been achieved. Since the LLR value of each of the variable nodes 22 involved in the process will be recalculated and updated during the calculation, each variable node 22 can only be involved in one calculation at a time in a layered decoding architecture. That is, the calculation that is being done on the variable nodes 22 connected by edges 24 to a first check node 26a cannot be done simultaneously in a second check node operating on any of the same variable nodes 22. For example, variable node 22a is connected by an edge 24a to check node 26a. However, variable node 22a is also connected by an edge 24b to check node 26d. And yet, none of the same variable nodes 22 are connected to both check node 26a and check node 26b. Accordingly, the LLR can be calculated for all of the variable nodes 22 connected to check node 26a and check node 26b, but cannot be simultaneously calculated for all of the variable nodes connected to check node 26a and check node 26d (since at least one variable node 22a is connected to both check node 26a and check node 26d). It will be noted from both FIG. 1 and FIG. 2 that there is no common variable node 22 connected to both check node 26a and check node 26b. Likewise, there is no common variable node 22 between check node 26c and check node 26d, nor between check node 26e and check node 26f. Accordingly, the LLR calculation in this case can be performed by each such pair of check nodes simultaneously using two parallel sets of hardware (one set of hardware for calculating the LLRs associated with the variable nodes connected to the first check node 26a and the other set of hardware to calculate the LLRs associated with the variable nodes connected to the second check node 26b). Once the LLRs for the variable nodes 22 connected to the first pair 26a, 26b have been calculated in association with the first pair of check nodes 26a, 26b, hardware can be use to calculate the LLRs for the variable nodes 22 in connection with the second pair of check nodes 26c, 26d. It should be noted that each check node 26 is connected to four variable nodes 22. Accordingly, LLRs for eight of the twelve variable nodes 22 can be calculated at a time. Due to these limitations on calculating LLRs simultaneously, and due to a need for flexibility in how codes words are defined, and further due to the desire to efficiently use a common hardware architecture for various applications, a new architecture and method for decoding is needed.